// Problem 175: Fractions involving the number of different ways a number can be expressed as a sum of powers of 2
// Define f(0)=1 and f(n) to be the number of ways to write n as a sum of powers of 2 where no power occurs more than twice.
// For example, f(10)=5 since there are five different ways to express 10:
// 10 = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1
// It can be shown that for every fraction p/q (p>0, q>0) there exists at least one integer n such that f(n)/f(n-1)=p/q.
// For instance, the smallest n for which f(n)/f(n-1)=13/17 is 241.
// The binary expansion of 241 is 11110001.
// Reading this binary number from the most significant bit to the least significant bit there are 4 one's, 3 zeroes and 1 one. We shall call the string 4,3,1 the Shortened Binary Expansion of 241.
// Find the Shortened Binary Expansion of the smallest n for which f(n)/f(n-1)=123456789/987654321.
// Give your answer as comma separated integers, without any whitespaces.
// -----
// 123456789/987654321 = coprime 13717421/109739369
// find A002487(n),A002487(n-1) = 13717421,109739369
// OMG! I read lot of article about Stern-Brocot Tree, finally I get the point as function find.
// [ref: https://oeis.org/A002487](https://oeis.org/A002487)

package main

import "fmt"

func p175() {
	count1, count0 := 0, 0
	find175(13717421, 109739369, &count1, &count0)
	fmt.Printf("Problem 175: 1,%d,%d\n", count0, count1)
}

// In the scenario offset is +1, that means f(10)=A002487(11)
// func A002487(n int) int {
// 	if n < 2 {
// 		return n
// 	}
// 	if n%2 == 0 {
// 		return A002487(n / 2)
// 	} else {
// 		return A002487((n-1)/2) + A002487((n+1)/2)
// 	}
// }

func find175(x, y int, c1, c0 *int) {
	a, b, c, d := 0, 1, 1, 0
	m, n := a+c, b+d
	for x != m || y != n {
		if x*n < y*m {
			*c1++
			c, d = m, n
		} else {
			*c0++
			a, b = m, n
		}
		m, n = a+c, b+d
	}

}
